package com.shixianchen.study.day1;

/**
 * @author ShiXianChen
 * @version V1.0.0
 * @Description 动态规格 - 背包问题  （1）暴力递归 （2）动态规划
 * @date 2022/10/29 23:26
 */
public class Code01_Knapsack {
    /**
     * 获取最大的数组  默认 weight 和 value 等长
     *
     * @param weight   重量数组
     * @param value    价值数组
     * @param bagLimit 背包生剩余的重量
     * @return 最大价值
     */
    public static int maxValue1(int[] weight, int[] value, int bagLimit) {
        return process1(weight, value, 0, bagLimit);
    }


    /**
     * 获取最大的数组  默认 weight 和 value 等长
     *
     * @param weight   重量数组
     * @param value    价值数组
     * @param bagLimit 背包生剩余的重量
     * @return 最大价值
     */
    public static int maxValue2(int[] weight, int[] value, int bagLimit) {
        int length = weight.length;

        int[][] dp = new int[length + 1][bagLimit + 1];

        for (int i = 0; i <= length; i++) {
            for (int j = 0; j <= bagLimit; j++) {
                dp[i][j] = -2;
            }
        }

        return process2(weight, value, 0, bagLimit, dp);
    }

    /**
     * 递归函数
     *
     * @param weight 重量数组
     * @param value  价值数组
     * @param index  index --> n, 可以选择的位置
     * @param rest   背包所剩的容量
     * @param dp     缓存数组
     * @return 返回当前的最大价值
     */
    private static int process2(int[] weight, int[] value, int index, int rest, int[][] dp) {
        // 剩余的负重是一个复数，说明之前是错误
        if (rest < 0) {
            //说明之前选错了
            return -1;
        }

        //之前算过缓存 命中
        if (dp[index][rest] != -2) {
            return dp[index][rest];
        }

        //缓存没命中
        int ans = 0;
        if (index == weight.length) {
            ans = 0;
        } else {
            //没有选index位置
            int p1 = process2(weight, value, index + 1, rest, dp);
            //选择index位置
            int p2 = -1;

            int next = process2(weight, value, index + 1, rest - weight[index], dp);

            if (next != -1) {
                p2 = value[index] + next;
            }
            ans = Math.max(p1, p2);
        }

        //放入缓存
        dp[index][rest] = ans;

        return ans;
    }

    /**
     * 递归函数
     *
     * @param weight 重量数组
     * @param value  价值数组
     * @param index  index --> n, 可以选择的位置
     * @param rest   背包所剩的容量
     * @return 返回当前的最大价值
     */
    public static int process1(int[] weight, int[] value, int index, int rest) {
        // 剩余的负重是一个复数，说明之前是错误
        if (rest < 0) {
            //说明之前选错了
            return -1;
        }

        if (index == weight.length) {
            //没货了
            return 0;
        }

        //即有货,又有负重

        //没要index位置的货
        int p1 = process1(weight, value, index + 1, rest);
        //要了当前index的货物
        //后面货怎么选择价值最大
        int p2 = -1;

        int next = process1(weight, value, index + 1, rest - weight[index]);

        if (next != -1) {
            p2 = value[index] + next;
        }

        return Math.max(p1, p2);
    }

    /**
     * 测试
     *
     * @param args
     */
    public static void main(String[] args) {
        int[] weight = {3, 2, 4, 7, 3, 3, 1, 7};
        int[] value = {5, 6, 3, 19, 12, 4, 2, 3};
        int bagLimit = 15;
        System.out.println(maxValue1(weight, value, bagLimit));
        System.out.println(maxValue2(weight, value, bagLimit));


    }
}
